/**
 * Created With IntelliJ IDEA
 * Description:leetcode：110. 平衡二叉树
 * <a href="https://leetcode.cn/problems/balanced-binary-tree/">...</a>
 * User: DELL
 * Data: 2023-01-13
 * Time: 20:34
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}
//本题最基本的做法就是递归每一个结点，求出每一个左右结点的高度，看每一个结点
//的左右结点的高度差是否大于1，但这样子的做法会导致时间复杂度为O（n^2)
//改进的方法就是自低而上的递归
public class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }
    //当左右结点的高度差大于1的时候返回-1
    private int height(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = height(root.left);
        if (leftHeight == -1) {
            return -1;
        }
        int rightHeight = height(root.right);
        if (rightHeight == -1) {
            return -1;
        }
        //高度差的绝对值大于1的时候返回-1
        if (Math.abs(leftHeight-rightHeight) > 1) {
            return -1;
        }
        return Math.max(leftHeight,rightHeight) + 1;
    }
}